home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 15 / CU Amiga Magazine's Super CD-ROM 15 (1997)(EMAP Images)(GB)[!][issue 1997-10].iso / CUCD / Graphics / Ghostscript / source / inamedef.h < prev    next >
Encoding:
C/C++ Source or Header  |  1997-04-24  |  7.8 KB  |  208 lines
  1. /* Copyright (C) 1989, 1995, 1997 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* inamedef.h */
  20. /* Name table definition */
  21. #include "iname.h"
  22. #include "gconfigv.h"        /* defines EXTEND_NAMES */
  23.  
  24. /*
  25.  * The name table machinery has two slightly different configurations:
  26.  * a faster one that limits the total number of names to 64K and allows
  27.  * names up to 16K in size, and a slightly slower one that limits
  28.  * the total to 4M and restricts names to 256 characters.
  29.  */
  30. #if arch_sizeof_int < 4
  31. #  undef EXTEND_NAMES        /* no extended names if ints are short */
  32. #endif
  33. #ifndef EXTEND_NAMES        /* # of bits beyond 16 */
  34. #  define EXTEND_NAMES 0
  35. #endif
  36. #define max_name_extension_bits 6
  37. #if EXTEND_NAMES > max_name_extension_bits
  38. #  undef EXTEND_NAMES
  39. #  define EXTEND_NAMES max_name_extension_bits
  40. #endif
  41. /*     
  42.  * We capture the small algorithmic differences between these two
  43.  * configurations entirely in this header file;
  44.  * the implementation doesn't need any conditionals on EXTEND_NAMES.
  45.  */
  46. #define max_name_index (uint)((0x10000 << EXTEND_NAMES) - 1)
  47. /* As explained below, we distinguish name indices from name counts. */
  48. #define max_name_count max_name_index
  49.  
  50. /* ---------------- Structure definitions ---------------- */
  51.  
  52. /*
  53.  * Define the structure of a name.  The next_index "pointer" is used for
  54.  * the chained hash table in the name_table, and also for the list of
  55.  * free names.  The pvalue member implements an important optimization
  56.  * to avoid lookup for operator and other global names.
  57.  */
  58. struct name_s {
  59.     ushort next_index;    /* (low bits of) next name in chain or 0 */
  60.     unsigned foreign_string : 1; /* string is allocated statically */
  61.     unsigned mark : 1;    /* GC mark bit */
  62. #if EXTEND_NAMES
  63. #  define name_extension_bits 6
  64.     unsigned my_extension : name_extension_bits;    /* high-order bits */
  65. #  define set_name_extension(pname, xbits) ((pname)->my_extension = xbits)
  66. #else
  67. #  define name_extension_bits 0
  68. #  define set_name_extension(name, xbits) DO_NOTHING
  69. #endif
  70.                 /* of index for this name */
  71. #define name_string_size_bits (14 - name_extension_bits)
  72. #define max_name_string ((1 << name_string_size_bits) - 1)
  73.     unsigned string_size : name_string_size_bits;
  74.     const byte *string_bytes;
  75. /* pvalue specifies the definition status of the name: */
  76. /*    pvalue == pv_no_defn: no definitions */
  77. #define pv_no_defn ((ref *)0)
  78. /*    pvalue == pv_other: other status */
  79. #define pv_other ((ref *)1)
  80. /*    pvalue != pv_no_defn, pvalue != pv_other: pvalue is valid */
  81. #define pv_valid(pvalue) ((unsigned long)(pvalue) > 1)
  82.     ref *pvalue;        /* if only defined in systemdict */
  83.                 /* or userdict, this points to */
  84.                 /* the value */
  85. };
  86. /*typedef struct name_s name;*/        /* in iref.h */
  87.  
  88. /*
  89.  * Define the structure of a name table.  Normally we would make this
  90.  * an opaque type, but we want to be able to in-line some of the
  91.  * access procedures.
  92.  *
  93.  * The name table is a two-level indexed table, consisting of
  94.  * sub-tables of size nt_sub_size each.
  95.  *
  96.  * First we define the name sub-table structure.
  97.  */
  98. #define nt_log2_sub_size (7 + (EXTEND_NAMES / 2))
  99. # define nt_sub_size (1 << nt_log2_sub_size)
  100. # define nt_sub_index_mask (nt_sub_size - 1)
  101. typedef struct name_sub_table_s {
  102.     name names[nt_sub_size];    /* must be first */
  103. #if EXTEND_NAMES
  104.     byte next_index_extension[nt_sub_size];    /* high-order bits */
  105.                     /* of next_index */
  106. #  define name_next_index(nidx, pname)\
  107.      (    (((name_sub_table *)((pname) - ((nidx) & nt_sub_index_mask)))->\
  108.       next_index_extension[(nidx) & nt_sub_index_mask] << 16) +\
  109.     ((pname)->next_index)\
  110.      )    
  111. #  define set_name_next_index(nidx, pname, next)\
  112.      ( ((name_sub_table *)((pname) - ((nidx) & nt_sub_index_mask)))->\
  113.       next_index_extension[(nidx) & nt_sub_index_mask] =\
  114.      (byte)((next) >> 16),\
  115.        (pname)->next_index = (ushort)(next)\
  116.      )
  117. #else        /* !EXTEND_NAMES */
  118. #  define name_next_index(nidx, pname)\
  119.      ((pname)->next_index)
  120. #  define set_name_next_index(nidx, pname, next)\
  121.      ((pname)->next_index = (next))
  122. #endif        /* (!)EXTEND_NAMES */
  123. } name_sub_table;
  124. /*
  125.  * Now define the name table itself.
  126.  * This must be made visible so that the interpreter can use the
  127.  * inline macros defined below.
  128.  */
  129. #define nt_hash_size (1024 << (EXTEND_NAMES / 2))  /* must be a power of 2 */
  130. struct name_table_s {
  131.     uint free;        /* head of free list, which is sorted in */
  132.                 /* increasing count (not index) order */
  133.     uint sub_next;        /* index of next sub-table to allocate */
  134.                 /* if not already allocated */
  135.     uint sub_count;        /* index of highest allocated sub-table +1 */
  136.     uint max_sub_count;    /* max allowable value of sub_count */
  137.     gs_memory_t *memory;
  138.     uint hash[nt_hash_size];
  139.     name_sub_table *sub_tables[max_name_index / nt_sub_size + 1];
  140. };
  141. /*typedef struct name_table_s name_table;*/    /* in iname.h */
  142.  
  143. /* ---------------- Procedural interface ---------------- */
  144.  
  145. /* Convert between names and indices.  Note that the inline versions, */
  146. /* but not the procedure versions, take a name_table argument. */
  147.         /* ref => index */
  148. #if EXTEND_NAMES
  149. #  define name_index_inline(pnref)\
  150.      ( ((uint)((pnref)->value.pname->my_extension) << 16) + r_size(pnref) )
  151. #else
  152. #  define name_index_inline(pnref) r_size(pnref)
  153. #endif
  154. #define name_index(pnref) name_index_inline(pnref)
  155.         /* index => name */
  156. #define name_index_ptr_inline(nt, nidx)\
  157.   ((nt)->sub_tables[(nidx) >> nt_log2_sub_size]->names + ((nidx) & nt_sub_index_mask))
  158.         /* index => ref */
  159. #define name_index_ref_inline(nt, nidx, pnref)\
  160.   make_name(pnref, nidx, name_index_ptr_inline(nt, nidx));
  161.         /* name => ref */
  162. /* We have to set the space to system so that the garbage collector */
  163. /* won't think names are foreign and therefore untraceable. */
  164. #define make_name(pnref, nidx, pnm)\
  165.   make_tasv(pnref, t_name, avm_system, (ushort)(nidx), pname, pnm)
  166.  
  167. /* ------ Garbage collection ------ */
  168.  
  169. /* Unmark all names, except for 1-character permanent names, */
  170. /* before a garbage collection. */
  171. void name_unmark_all(P0());
  172.  
  173. /* Finish tracing the name table by putting free names on the free list. */
  174. void name_trace_finish(P1(gc_state_t *));
  175.  
  176. /* ------ Save/restore ------ */
  177.  
  178. /* Clean up the name table before a restore, */
  179. /* by removing names whose count is less than old_count. */
  180. #ifndef alloc_save_t_DEFINED        /* also in isave.h */
  181. typedef struct alloc_save_s alloc_save_t;
  182. #  define alloc_save_t_DEFINED
  183. #endif
  184. void name_restore(P1(alloc_save_t *));
  185.  
  186. /* ---------------- Name count/index maintenance ---------------- */
  187.  
  188. /*
  189.  * We scramble the assignment order within a sub-table, so that
  190.  * dictionary lookup doesn't have to scramble the index.
  191.  * The scrambling algorithm must have three properties:
  192.  *    - It must map 0 to 0;
  193.  *    - It must only scramble the sub-table index;
  194.  *    - It must be a permutation on the sub-table index.
  195.  * Something very simple works just fine.
  196.  */
  197. #define name_count_to_index(cnt)\
  198.   (((cnt) & (-nt_sub_size)) +\
  199.    (((cnt) * 59) & nt_sub_index_mask))
  200. /*
  201.  * The reverse permutation requires finding a number R such that
  202.  * 59*R = 1 mod nt_sub_size.  For nt_sub_size any power of 2 up to 2048,
  203.  * R = 243 will work.  Currently, this is only needed for debugging printout.
  204.  */
  205. #define name_index_to_count(nidx)\
  206.   (((nidx) & (-nt_sub_size)) +\
  207.    (((nidx) * 243) & nt_sub_index_mask))
  208.